#include "bitset.h"
#include <limits.h>
#include <stdlib.h>
#include <assert.h>

typedef unsigned    BITTYPE;    /* one could tinker with different sizes... */

typedef struct  TBitSet
    {
    int         NChunks;
    int         NBits;
    BITTYPE     Bits[1];
    }           TBitSet;

static int      BitWidth;       /* how many bits wide is a BITTYPE?     */
static BITTYPE* Masks;          /* array of one-bit masks               */

/* Init() - initialize some bitmap masks for internal use. */
static
void    Init(void)
    {
    int     iMask;
    BITTYPE Mask;

    BitWidth    = sizeof(BITTYPE)*CHAR_BIT;

    Masks   = malloc(BitWidth*sizeof(BITTYPE));
    assert(Masks != NULL);
    /* why do it backwards? because >> is impl-defined for negatives */
    Mask    = 1;
    for(iMask=BitWidth-1; iMask >= 0; --iMask)
        {
        Masks[iMask]    = Mask;
        Mask <<= 1;
        }
    }

BITSET  BitSetNew(size_t Size)
    {
    int         NChunks;
    TBitSet*    Result;

    if(!Masks)
        Init();
    /* round up to nearest BITTYPE size */
    NChunks = ((Size + (BitWidth-1))/BitWidth);

    Result      = (TBitSet*)calloc(offsetof(TBitSet,Bits) + NChunks * sizeof(BITTYPE), sizeof(char));
    assert(Result != NULL);
    Result->NBits   = Size;
    Result->NChunks = NChunks;
    
    return (BITSET)Result;
    }
    
void    BitSetDelete(BITSET Handle)
    {
    free((TBitSet*)Handle);
    }

BITSET  BitSetOr(BITSET Handle, BITSET Other)
    {
    int         iChunk;
    TBitSet*    A  = (TBitSet*)Handle;
    TBitSet*    B  = (TBitSet*)Other;

    assert(A->NBits == B->NBits);
    for(iChunk=0; iChunk < A->NChunks; ++iChunk)
        A->Bits[iChunk] |= B->Bits[iChunk];

    return Handle;
    }

BITSET  BitSetCopy(BITSET Handle, BITSET Other)
    {
    int         iChunk;
    TBitSet*    A  = (TBitSet*)Handle;
    TBitSet*    B  = (TBitSet*)Other;

    assert(A->NBits == B->NBits);
    for(iChunk=0; iChunk < A->NChunks; ++iChunk)
        A->Bits[iChunk] = B->Bits[iChunk];

    return Handle;

    }

BITSET  BitSetSet(BITSET Handle, int Offset)
    {
    TBitSet* A  = (TBitSet*)Handle;

    assert(A->NBits > Offset);
    A->Bits[Offset/BitWidth]    |= Masks[Offset%BitWidth];

    return Handle;

    }

int     BitSetCount(BITSET Handle)
    {
    int         iMask, iChunk, Result=0;
    TBitSet*    A  = (TBitSet*)Handle;

    for(iChunk=0; iChunk < A->NChunks; ++iChunk)
        {
        BITTYPE Chunk = A->Bits[iChunk];
        
        for(iMask=0; iMask < BitWidth; ++iMask)
            if(Chunk&Masks[iMask])
                ++Result;
        }

    return Result;
    }


BITITER BitIterNew(BITSET Handle)
    {
    BITITER Iter;

    Iter.BitSet = Handle;
    Iter.Index  = 0;
    return Iter;
    }

int     BitIterNext(BITITER* Iter)
    {
    int         Result  = -1;   /* assume failure */
    TBitSet*    A = (TBitSet*)Iter->BitSet;

    while(Iter->Index < A->NBits && Result == -1)
        {
        int     iChunk  = Iter->Index / BitWidth;
        BITTYPE Mask    = Masks[Iter->Index % BitWidth];

        if(A->Bits[iChunk]&Mask)
            Result  = Iter->Index;
        ++Iter->Index;
        }

    return Result;
    }

